#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/10
# @Author   :Changshu
# @File     :practice_107.py

# 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

from collections import deque

class TreeNode:
	def __init__(self,x):
		self.val=x
		self.left=None
		self.right=None


def levelOrderBottom(root: TreeNode):
	result=[]
	if root==None:
		return result
	queue=deque()
	queue.append(root)
	while len(queue)!=0:
		l=[]
		onelevel=len(queue)
		while onelevel>0:
			# popleft 表示先进先出
			p=queue.popleft()
			l.append(p.val)
			if p.left!=None:
				queue.append(p.left)
			if p.right!=None:
				queue.append(p.right)
			onelevel-=1
		result.insert(0,l)
	return result



if __name__ == '__main__':
	root = TreeNode(3)
	node1_1=TreeNode(9)
	node1_2=TreeNode(20)

	root.left=node1_1
	root.right=node1_2

	node2_1=TreeNode(15)
	node2_2 = TreeNode(7)
	node1_2.left=node2_1
	node1_2.right=node2_2

	r=levelOrderBottom(root)
	print(r)
